package arithmetic;

/**
 * Created by AJie on 2019/3/30
 * Function : 股票交易
 * LeetCode 121  122  123 309 188 714
 *
 * 121 只能买卖1次
 *      思考,找到max min，deal or not。 O(n).
 * 122 买卖无数次
 *      ,注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 *      思考,只要是 n>n-1,那么，n-1就可以买。n就可以卖。
 * 123 你最多可以完成 2次交易。
 *      ,（2次买 ，2次卖。）
 *      ,注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 *      思路-思考：
 *      最大子序列，2个之和。不能交叉。
 *      如果交叉，取最大的 ? 2个小的> 1个最大的+1个小的 ？？？存在这种漏洞么？
 *      暴力法？找到所有的子序列。然后再去交叉？再排序大小。最大的2个相加？
 * 188  买卖股票的最佳时机 IV , 完成 K 次交易
 * 状态转移直接解决
 *
 * 基础值的设定：
 * dp[-1][k][0] = 0
 * 解释：因为 i 是从 0 开始的，所以 i = -1 意味着还没有开始，这时候的利润当然是 0 。
 * dp[-1][k][1] = -infinity
 * 解释：还没开始的时候，是不可能持有股票的，用负无穷表示这种不可能。
 * dp[i][0][0] = 0
 * 解释：因为 k 是从 1 开始的，所以 k = 0 意味着根本不允许交易，这时候利润当然是 0 。
 * dp[i][0][1] = -infinity
 * 解释：不允许交易的情况下，是不可能持有股票的，用负无穷表示这种不可能。
 *
 * 作者：labuladong
 * 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/solution/yi-ge-tong-yong-fang-fa-tuan-mie-6-dao-gu-piao-w-5/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * base case：
 * dp[-1][k][0] = dp[i][0][0] = 0
 * dp[-1][k][1] = dp[i][0][1] = -infinity
 *
 * 状态转移方程：
 * dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
 * dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
 *
 */
public class A_29_Transaction {
    public static void main(String[] args) {
        int [] nums = new int[] {7,1,5,3,6,4};
//        int i = maxProfit(nums);
        int i = maxProfit_k_inf(nums);
        System.out.println(i);
    }
    public static int maxProfit(int[] prices) {
        int K = prices.length ;//最多交易k次
        int J = 1;//最多持有多少股
        int [][][]mp = new int[prices.length+1][K+1][J+1];

        mp[0][0][0]=0;
        mp[0][0][1]=-prices[0];
        mp[0][1][0]= Integer.MIN_VALUE;
        mp[0][1][1]= Integer.MIN_VALUE;
        for (int i = 1; i < K; i++) {
            mp[0][i][0] = Integer.MIN_VALUE;
            mp[0][i][1] = Integer.MIN_VALUE;
        }
        int res=0;
        for (int i = 1; i <= prices.length; i++) {
            for (int k = 1; k <= K; k++) {
//                System.out.println("i=="+i +"  k=="+k +"  "+mp.length);
                mp[i][k][0]=Math.max(mp[i-1][k][0],mp[i-1][k-1][1]+prices[i]);
                mp[i][k][1]=Math.max(mp[i-1][k][1],mp[i-1][k-1][0]-prices[i]);

                    res = Math.max(res,Math.max(mp[i][k][0], mp[i][k][1]));
//                for (int j = 0; j <= J; j++) {
//
//                }
            }
        }


        return res;
    }

    public static int maxProfit_k_inf(int[] prices) {
        int n = prices.length;
        int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            int temp = dp_i_0;
            dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
            dp_i_1 = Math.max(dp_i_1, temp - prices[i]);
        }
        return dp_i_0;
    }

}
